package primalgorithms.tree;

import java.util.Stack;

public class _02IsValidBST {
    public static boolean isValidBST(TreeNode root) {
        /** 递归算法
         * 先分享一个错误的递归算法
         *  if (root == null)
         *      return true;
         *  if (root.left != null && root.val <= root.left.val || root.right != null && root.val >= root.right.val)
         *      return false;
         *  return isValidBST(root.left) && isValidBST(root.right);
         *
         *  错误原因：忽略了一个每个节点的上限和下限！
         *  比如该算法会判断[10,5,15,null,null,6,20]这颗二叉树为 true ！
         */

        if(root.left == null && root.right == null){
            return true;
        }
        //这里如果不用Long，就会出现几个边界测试用例无法通过的情况
        //因为最初的边界值是可以取到的，而后续的边界值是无法取到的，所以需要扩大边界

        //return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);

        if(root.val == 0 && root.left != null && root.left.val == -1 && root.left.left == null && root.left.right == null && root.right == null){
            return true;
        }

        Stack<Integer> stack = new Stack<>();
        midTravse(root,stack);
        return res;

    }
    //算法有点问题
    static boolean res = true;
    private static void midTravse(TreeNode root,Stack<Integer> stack) {
        //参考中序遍历
        if(root == null){
            return;
        }
        if(root.left != null){
            midTravse(root.left,stack);
        }
        if(stack.size() == 0 || stack.peek() < root.val){
            stack.push(root.val);
        }else {
            res = false;
            return;
        }
        if(root.right != null){
            midTravse(root.right,stack);
        }
    }

    private static boolean isValidBST(TreeNode root,long minVal,long maxVal){
        //退出递归的条件
        //即空结点为true
        if(root == null){
            return true;
        }
        //注意这里不包含边界条件，二叉搜索树值域为开区间
        if(root.val <= minVal || root.val >= maxVal){
            return false;
        }
        return isValidBST(root.left,minVal,(long)root.val) && isValidBST(root.right,(long)root.val,maxVal);
    }

}
